package cn.itcast.com.MyLinkedList;

import cn.itcast.com.MyArrayList.Mylist;
import lombok.NoArgsConstructor;

import java.util.ConcurrentModificationException;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class MyLinkedList<E> implements Mylist<E> {
    //使用一个内部类表示节点
    class Node {
        //前驱节点
        Node prev;
        //后驱节点
        Node next;
        //value
        E value;

        //构造1
        public Node(E value) {
                this.value = value;
        }
        //构造2
        public Node(Node prev, E value, Node next){
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node header;
    private Node tail;
    //记录当前集合的数据个数
    private int size;
    //用来记录结构变化的次数
    private int modCount;

    //构造方法
    public MyLinkedList() {
        //需要初始化header和tail，这两个是Node，所以需要使用Node的构造方法
        header = new Node(null,null,null);
        tail = new Node(null,null,null);

        //双向链表需要首位相连，又初始只有header和tai这两个，所以这两个首尾相连
        //header是MyLinkedList类的一个属性，他是一个节点，这个节点有前驱和后继，值这三个属性
        header.next = tail;
        tail.prev = header;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("[");

        if (!isEmpty()){
            Node node=header.next;

            while (node!=tail){

                sb.append(node.value+",");
                node=node.next;

            }
            //包括左边，不包括右边 “123456”  0 5
            //
            sb.delete(sb.length()-1,sb.length());

        }


        sb.append("]");
        return  sb.toString();
    }
    //判断插入位置的合法性
    private void checkIndexForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index=" + index);
        }
    }

    //判断传入参数的合法性
    private void checkIndexForGet(int index) {
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("index=" + index);
        }
    }

    //add元素到链表的末尾
    @Override
    public boolean add(E e) {
        add(size, e);
        return true;
    }

    @Override
    public void add(int index, E element) {
        //检查
        checkIndexForAdd(index);

        //插入操作
        if (isEmpty()){
            //创建一个node，将值element 前后位置传入构造方法
            //此时为空，所以前为header，后为tail
            Node nodeToadd = new Node(header, element, tail);
            //此时nodeTOadd的前驱和后继已经改变，需要将header的后继和tail的前驱指向nodetoAdd
            header.next = nodeToadd;
            tail.prev = nodeToadd;

        }else {
            //假如添加的位置是末尾
            if (index == size){
                //如果在末尾的话，node就是tail
                Node node = tail;
                Node nodeToAdd = new Node(node.prev, element, node);
                node.prev.next = nodeToAdd;
                node.prev = nodeToAdd;

            }else {
                //假如添加的位置是一个普通的位置，可以通过getNode获得索引位置的node
                Node node = getNode(index);
                //该元素的前驱是之前node指向的前驱，而该元素的后继就是node
                Node nodeToAdd = new Node(node.prev, element, node);
                //将node指向的前驱的后继指向nodeToAdd，将node的前驱指向nodeToAdd
                node.prev.next = nodeToAdd;
                node.prev = nodeToAdd;
            }

        }

        //增加之后，数量加一，结构发生改变
        size++;
        modCount++;
    }

    //根据索引去找对应的node
    private Node getNode(int index) {
        checkIndexForGet(index);

        Node node = null;
        //如果非空查询，空则返回null node
        if (!isEmpty()){
            //初始化第一个要找的
            node = header.next;
            //找index只需要查index次
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }
        return node;
    }

    //清空只需要像初始化一样，收尾相连
    @Override
    public void clear() {
        header.next = tail;
        tail.prev = header;
        size = 0;
        modCount++;
    }

    @Override
    public boolean contains(Object o) {
        int i = indexOf(o);
        return i != -1;
    }

    @Override
    public E get(int index) {
        checkIndexForGet(index);

        Node node = header.next;
        int i = 0;
        while (node != tail){
            if (index == i){
                return node.value;
            }
            i++;
            node = node.next;
        }
        return null;
    }

    //查找索引位置
    @Override
    public int indexOf(Object o) {
        //初始化
        Node node = header.next;
        //找不到就是-1
        int index = -1;

        if (o != null){
            //假如node到了tail表示到底了
            while (node != tail){
                index++;
                if (o.equals(node.value)){
                    return index;
                }
                node = node.next;
            }
        }else {
            while (node != tail){
                index++;
                if (o == node.value){
                    return index;
                }
                node = node.next;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public E remove(int index) {
        //判断合法
        checkIndexForGet(index);
        Node node = getNode(index);
        if (node == null){
            return null;
        }else {
            E e = node.value;
            //更改前驱后继
            node.prev.next = node.next;
            node.next.prev = node.prev;
            return e;
        }
    }

    @Override
    public boolean remove(Object o) {
        int i = indexOf(o);
        remove(i);
        return false;
    }

    @Override
    public E set(int index, E element) {
        Node node = getNode(index);
        node.value = element;
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public ListIterator<E> listIterator() {
        return new Itr();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return new Itr(index);
    }

    private class Itr implements ListIterator<E>{

        //游标
        int cursor;
        //记录游标next的元素位置
        Node currentNode;
        //记录修改
        int expModCount = modCount;
        //记录next previous的返回值
        Node lastRetNode;

        public Itr() {
            //初始游标指向第一个
            currentNode = header.next;
        }

        public Itr(int index) {
            cursor = index;
            //假如初始化的位置在末尾，游标就是tail
            if (index == size){
                currentNode = tail;
            }else {
                currentNode = getNode(index);
            }
        }
        //检查
        private void checkConcurrentModificationException() {
            if (expModCount!=modCount){
                throw  new ConcurrentModificationException();
            }

        }

        @Override
        public boolean hasNext() {
            return cursor<size;
        }

        @Override
        public E next() {
            checkConcurrentModificationException();

            //判断是否有下个元素
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            //利用currentNode找到当前值
            lastRetNode = currentNode;
            //后移currentNode的位置
            currentNode = currentNode.next;
            //游标也移动一位
            cursor++;

            return lastRetNode.value;
        }

        @Override
        public boolean hasPrevious() {
            return cursor > 0;
        }

        @Override
        public E previous() {

            checkConcurrentModificationException();

            if (!hasPrevious()){
                throw new NoSuchElementException();
            }

            lastRetNode = currentNode.prev;
            currentNode = currentNode.prev;

            return lastRetNode.value;
        }

        @Override
        public int nextIndex() {
            return cursor;
        }

        @Override
        public int previousIndex() {
            return cursor-1;
        }

        @Override
        public void remove() {
            //检查lastRetRet
            if (lastRetNode == null){
                throw new IllegalStateException("lastRetNode=-1");
            }
            //检查并发
            checkConcurrentModificationException();

            //通过lastRetNode进行删除操作
            MyLinkedList.this.remove(lastRetNode);

            //感觉不变cursor
            cursor++;
            lastRetNode = null;
            expModCount++;
        }

        @Override
        public void set(E e) {
            if (lastRetNode == null){
                throw new IllegalStateException();
            }
            checkConcurrentModificationException();
            lastRetNode.value = e;

        }

        @Override
        public void add(E e) {
            //调用mylinklist的方法添加
            //cursor作为插入的index
            MyLinkedList.this.add(cursor,e);
            //添加完毕，游标加一
            cursor++;
            //add之后即为null😡
            lastRetNode = null;
            expModCount = modCount;
        }
    }


}
